/*
 * @lc app=leetcode.cn id=160 lang=typescript
 *
 * [160] 相交链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

//  思路：双指针
//  关键点是保证走的步数一致，每个链表走一遍，换头法!!
//  链表A为空则继续走B链表，B链表为空则继续走A链表，当走到最后都为空，说明无交点，有交点则会相等

//  复杂度：O(n) O(1)

function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
    let hA = headA, hB = headB
    if (!hA || !hB) return null

    while (hA !== hB) {
        hA = hA ? hA.next : headB
        hB = hB ? hB.next : headA
    }
    return hA
};
// @lc code=end
import { ListNode } from './type'

const com = new ListNode(2, new ListNode(4))
const headA = new ListNode(2, new ListNode(6, new ListNode(4, com)))
const headB = new ListNode(1, new ListNode(5, com))
const res = getIntersectionNode(headA, headB)
console.log(res ? res.val : 'null');
